#include "rbTree.h"

//只插入、不调整。static使当前函数只能被本文件调用，对外不可见（黑盒）
static void rbtree_insert(RBRoot* root, Node* node)
{
    //二叉查找树放入
    //指向根节点
    RBTree  x=root->node;
    //存储x的前一个结点
    RBTree y =NULL;
    //找到新节点node插入的位置
    while(x)
    {
        //这里已经更新y，在下面无需再次更新
        y=x;
        if(node->key>x->key)
        {
            x=x->right;
        }
        else{
            x=x->left;
        }
    }
    //树空，新节点为根
    if(NULL==y)
    {
        root->node=node;
    }else{
        //新节点应该放在左边还是右边
        if(y->key>node->key)
        {
            y->left=node;
        }else{
            y->right=node;
        }
        node->parent=y;
    }
    //调用函数，修正为红黑树
    rbtree_insert_fixup(root,node);

}

//（假的）插入新建节点，调用插入函数
void insert_rbtree(RBRoot* root,Type element)
{
    RBTree node=(RBTree)calloc(1,sizeof(Node));
    node->key=element;
    node->color=RED;
    rbtree_insert(root,node);
}